1087 - Diablo
 |
PDF (English) |
Statistics |
Forum |
| Time Limit: 2 second(s) |
Memory Limit: 64 MB |
All of you must have played the game 'Diablo'. It's an exclusive game to play. In this game the main opponent of you is Diablo. If you kill him the game finishes. But as usual, Diablo is smarter than you.
Diablo has a large number of army. Diablo arranges them in a line in any arbitrary order and everyone is given an integer id. Each time Diablo either adds one army in the end or he calls for the kth army (from left) from the line. Then the army gets out and it attacks you.
Since you are a great magician, you can read Diablo's mind. Now you want to find the id of the armies who are about to attack you.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
The first line of each case is a blank line. The next line contains two integers n (0 ≤ n ≤ 105), denoting the number of the initial army and q (1 ≤ q ≤ 50000) representing the number of queries. The next line contains n space separated integers. The ith integer of this line denotes the id of the ith person. Each of these integers will be positive and fits into a 32 bit signed integer. Each of the next q lines will contain a query, of the form:
a p (add a person at the end of the line whose id is p)
c k (call the kth person from the line (from left), k is a positive 32 bit signed integer)
Output
For each case of input, print the case number in a line. Then for all the queries 'c k' you have to print the id of the kth person or 'none' if there is none.
Sample Input |
Output for Sample Input |
| 2 5 5 6 5 3 2 1 c 1 c 1 a 20 c 4 c 4 2 1 18811 1991 c 1 |
Case 1: 6 5 20 none Case 2: 18811 |
看完题立马想到平衡树，以数的插入顺序建立一颗平衡树，查询和删除第K小即可，然后又想到维护一个区间和，二分求出区间和为k的位置，然后该位置的数就是所求，这种方法可以用线段树或者树状数组实现，不多说了，水题直接上代码。
各种蛋疼：好久没写这些数据结构了，手好生啊，调了半天。
平衡树版本-SBT
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 111111;
struct TNode{
int l,r,idx,val,size;
void clearNode(){
l = r = size = 0;
}
void initNode(int idx,int val){
this->idx = idx, this->val = val;
l = r = 0; size = 1;
}
};
struct SBT{
TNode Node[MAXN];
int pool[MAXN],top,cnt,rt;
void init(){
top = cnt = rt = 0;
}
int Malloc(int id,int v){
int x;
if(top!=0){
x = pool[--top];
}else{
x = ++cnt;
}
Node[x].initNode(id,v);
return x;
}
void Free(int x){
pool[top++] = x;
Node[x].clearNode();
}
void left_rotate(int &p){
TNode &fa = Node[p];
TNode &son = Node[fa.r];
int q = fa.r;//node idx of son
fa.r = son.l; son.l = p;
son.size = fa.size;
fa.size = Node[fa.l].size+Node[fa.r].size+1;
p = q;
}
void right_rotate(int &p){
TNode &fa = Node[p];
TNode &son = Node[fa.l];
int q = fa.l;
fa.l = son.r, son.r = p;
son.size = fa.size;
fa.size = Node[fa.l].size+Node[fa.r].size+1;
p = q;
}
void Maintain(int &p,bool flag){
TNode cur = Node[p];
if(!flag){
if(Node[Node[cur.l].l].size>Node[cur.r].size){
right_rotate(p);
}else if(Node[Node[cur.l].r].size>Node[cur.r].size){
left_rotate(cur.l);
right_rotate(p);
}else{
return;
}
}else{
if(Node[Node[cur.r].r].size>Node[cur.l].size){
left_rotate(p);
}else if(Node[Node[cur.r].l].size>Node[cur.l].size){
right_rotate(cur.r);
left_rotate(p);
}else{
return;
}
}
Maintain(cur.l,0);
Maintain(cur.r,1);
Maintain(p,0);
Maintain(p,1);
}
void Insert(int &p,int idx,int val){
if(!p){
p = Malloc(idx,val);
return;
}else{
Node[p].size++;
if(idx=Node[p].idx);
}
}
int Delete(int &p,int idx){
Node[p].size--;
if(Node[p].idx==idx||(Node[p].l==0&&idxNode[p].idx)){
int q = p;
if(Node[p].l==0||Node[p].r==0){
p = Node[p].l+Node[p].r;
Node[q].clearNode();
return q;
}else{
int cur = Delete(Node[p].r,idx+1);
int tidx = Node[p].idx, tval = Node[p].val;
Node[p].idx = Node[cur].idx, Node[p].val = Node[cur].val;
Node[cur].idx = tidx, Node[cur].val = tval;
return cur;
}
}
if(idx
线段树版本：
#include
#include
#include
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int MAXN = 111111;
const int BD = MAXN+50000;
int sum[(BD)<<2],record[BD];
void build(int l,int r,int rt){
sum[rt]=0;
if(l==r)return;
int m = (l+r)>>1;
build(lson); build(rson);
}
void update(int pos,int c,int l,int r,int rt){
if(l==r){
//cout<>1;
if(pos<=m)update(pos,c,lson);
else update(pos,c,rson);
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
int query(int k,int l,int r,int rt){
if(l==r)return l;
int m = (l+r)>>1;
if(sum[rt<<1]>=k)return query(k,lson);
else return query(k-sum[rt<<1],rson);
}
int main(){
int T,N,Q,M;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%d%d",&N,&Q);M = N+1;
build(1,BD,1);
for(int i=1;i<=N;i++)scanf("%d",&record[i]),update(i,1,1,BD,1);
printf("Case %d:\n",cas);
while(Q--){
char op[3];
int k;
scanf("%s%d",op,&k);
//cout<<"tot:"<
树状数组版本：
#include
#include
#include
using namespace std;
const int MAXN = 155555;
int sum[MAXN+1],arr[MAXN];
int lowbit(int x){
return x&(-x);
}
int query(int pos){
int s = 0;
while(pos>0){
s+=sum[pos];
pos -= lowbit(pos);
}
return s;
}
void add(int pos,int c){
while(pos<=MAXN){
sum[pos]+=c;
pos += lowbit(pos);
}
}
int main(){
int T,N,Q,M,CNT;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%d%d",&N,&Q);M = N+1;CNT = N;
memset(sum,0,sizeof(sum));
for(int i=1;i<=N;i++){
scanf("%d",&arr[i]);
add(i,1);
}
printf("Case %d:\n",cas);
while(Q--){
char op[3];int k;
scanf("%s%d",op,&k);
//cout<>1;
if(k<=query(m))r = m-1;
else l = m+1;
}
//cout<
京公网安备 11010802041100号